Kuznetsov sinh ra tại làng Medvedki, huyện Kotlas, tỉnh Arkhangelsk. Ông là con trai của một người nhập cư dân tộc Serbia. Năm 1919, ông gia nhập đội tàu hải quân Bắc Dvina của Xô Viết, hồi đó ông phải khai tăng thêm hai tuổi mới được tiếp nhận. Trong hồ sơ quân nhân, ghi năm sinh của ông là 1902. Từ năm 1920, ông đóng quân tại Petrograd, đến năm 1924, ông là một thành viên của một đơn vị hải quân Nga, ông đã từng được dự lễ tang của Vladimir Lenin. Cũng vào thời gian này, ông gia nhập đảng Bolshevik.

Sau khi tốt nghiệp học viện quân sự Frunze vào năm 1926, Kuznetsov được điều sang chiến đấu trên chiếc tàu tuần dương Chervona Ukraina, đầu tiên ông chỉ đơn thuần là một sĩ quan, sau đó là ông mang quân hàm thiếu úy. Ông đã tốt nghiệp các môn chiến dịch và chiến thuật, tại khoa chiến dịch hành quân của trường cao đẳng hải quân vào năm 1932. Sau khi tốt nghiệp, ông được quyền lựa chọn cho mình một vị trí công tác: ông có thể tự chọn một công việc nào đó trong ban tham mưu, hoặc sở chỉ huy trên một chiếc tàu chiến.

Kuznetsov đã quyết định nhận vụ là chỉ phó, trên chiếc tuần dương hạm mang tên "Krasny Kavkaz". Trong vòng một năm, ông đã được thăng cấp. Vào năm 1934, ông quay trở lại với chiếc tuần dương hạm "Chervona Ukraina", và là chỉ huy trưởng trên con tàu này. Dưới sự chỉ huy của Kuznetsov, chiếc tuần dương hạm đã trở thành một con tàu chiến điển hình nổi tiếng về ý thức kỷ luật, và sự tổ chức. Sự chú ý trong quân đội, nhanh chóng đổ dồn về vị thuyển trưởng trẻ tuổi này.

Từ ngày 5 tháng 9 năm 1936, đến ngày 15 tháng 8 năm 1937, Kuznetsov làm tùy viên hải quân và trưởng ban cố vấn hải quân của nước cộng hòa Tây Ban Nha. Trong thời gian phục vụ tại Tây Ban Nha, ông đã mở rộng và phát triển lòng căm thù đối với chủ nghĩa phát xít ở đây. Khi quay trở về nước, vào ngày 10 tháng 1 năm 1938, ông được giữ chức vụ tổng chỉ huy hạm đội Thái Bình Dương. Trong thời gian ông năm giữ cương vị này, ông trở thành một người phải đối mặt với vụ thanh trừng của Stalin trong quân đội. Chính bản thân Kuznetsov không bao giờ bị liên quan, nhưng có nhiều sĩ quan chỉ huy dưới quyền ông đã bị dính líu. Kuznetsov đã từng bước chống lại cuộc thành trừng này, và sự can thiệp của ông, đã cứu được mạng sống cho rất nhiều các sĩ quan Xô Viết.

Ngày 28 tháng 4 năm 1939, Kuznetsov mới chỉ tròn ba mươi tư tuổi, ông đã được bổ nhiệm là ủy viên hội đồng nhân dân (bộ trưởng) của hải quân, ông giữ vị trí công tác này trong suốt thế chiến thứ hai.